package everydayone.LRUCache;

import java.util.HashMap;
import java.util.Map;

/**
 * @Date 2020/05/25
 * @author 王光浩
 * @Thinking 使用 双链表+HashMap
 * @Analysis 时间复杂度O（1），空间复杂度O（n）
 */
public class MyMethodTwo {

	// 双向链表的节点
	private class DNode {
		int key;
		int value;
		DNode pre;
		DNode next;
		public DNode() {
		}
		public DNode(int key, int value) {
			this.key = key;
			this.value = value;
		}
	}
	private Map<Integer, DNode> map; // HashMap + 双向链表
	private DNode head; // 链表头节点
	private DNode tail; // 链表尾节点
	private int size;
	public MyMethodTwo(int capacity) {
		this.size = capacity;
		map = new HashMap<Integer, DNode>(capacity * 4 / 3);
		head = new DNode(-1, -1);
		tail = new DNode(-1, -1);
		head.next = tail;
		tail.pre = head;
	}
	public int get(int key) {
		DNode n = map.get(key);
		if (n == null)
			return -1;
		this.removeNode(n);
		this.addToHead(n);
		return n.value;
	}
	public void put(int key, int value) {
		DNode node = new DNode(key,value);
		DNode n = map.get(key);
		//如果是更新操作
		if (n != null) {
			map.remove(this.removeNode(n));
		} 
		map.put(key, node);
		this.addToHead(node);
		if (this.size < map.size()) {
			map.remove(this.removeTail());
		}
	}
	/**
	 * 将节点移动到双链表的首部
	 * @param node target node
	 */
	public void addToHead(DNode node) {
		// 将该节点添加到双链表首部
		node.pre = head;
		node.next = head.next;
		node.next.pre = node;
		node.pre.next = node;
	}

	public int removeNode(DNode node) {
		// 将该节点从 双链表中剥离
		node.pre.next = node.next;
		node.next.pre = node.pre;
		return node.key;
	}
	/**
	 * 断开双向链表的最后一个节点
	 */
	public int removeTail() {
		DNode node = tail.pre;
		node.pre.next = node.next;
		node.next.pre = node.pre;
		return node.key;
	}
}
